package com.cuz.daileetcode;

import com.cuz.daileetcode.utils.TreeNode;

import java.util.LinkedList;

/***
 * 是否是完全二叉树
 */
public class Day31_1 {


    public static class BST {
        public static boolean isBST1(TreeNode root) {
            if (root == null) {
                return true;
            }
            return isBST1(root.left, null, root.val)
                    && isBST1(root.right, root.val, null);
        }

        public static boolean isBST1(TreeNode root, Integer low, Integer high) {
            if (root == null) {
                return true;
            }
            if (low != null && root.val <= low) {
                return false;
            }
            if (high != null && root.val >= high) {
                return false;
            }
            boolean leftIsBst = isBST1(root.left, null, root.val);
            if (!leftIsBst) {
                return false;
            }
            boolean rightIsBst = isBST1(root.right, root.val, null);
            if (!rightIsBst) {
                return false;
            }
            return true;
        }


        //中序遍历成递增序列 preValue记录上前一个节点的值
        private static int preValue = Integer.MIN_VALUE;

        public static boolean isBST2(TreeNode root) {
            //空树 true
            if (root == null) {
                return true;
            }
            //左孩子不是BST false
            if (!isBST2(root.left)) {
                return false;
            }
            //如果当前节点小于等于上一次的值 那么false
            //bug：如果树只要一个节点 且节点就是Integer.MIN_VALUE;
            if (root.val <= preValue) {
                return false;
            }
            //设置为当前节点的值
            preValue = root.val;
            //判断右树
            return isBST2(root.right);
        }


        public static boolean isBST3(TreeNode root) {
            //空树 true
            if (root == null) {
                return true;
            }
            int preValue = Integer.MIN_VALUE;
            LinkedList<TreeNode> stack = new LinkedList<>();
            while (!stack.isEmpty() || root != null) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                if (root.val <= preValue) {
                    return false;
                }
                preValue = root.val;
                root = root.right;
            }
            return true;
        }

    }
}
